#include <bits/stdc++.h>
// 2025/07/22
// tag: 
// Author: Forever
using namespace std;
#define int long long

const int MOD = 571373;
const int MAXN = 200010; 

int n, m, a[MAXN], d[MAXN * 4], mul_tag[MAXN * 4], add_tag[MAXN * 4]; 

void push_up(int p)
{
    d[p] = d[p << 1] + d[(p << 1) | 1];
}

void push_down(int s, int t, int p)
{
    if (mul_tag[p] == 1 && add_tag[p] == 0) 
        return;
    int m = s + ((t - s) >> 1); 
    int len_left = m - s + 1; 
    int len_right = t - m; 
    d[p << 1] = ((d[p << 1] * mul_tag[p]) % MOD + (len_left * add_tag[p]) % MOD) % MOD;
    mul_tag[p << 1] = (mul_tag[p << 1] * mul_tag[p]) % MOD;
    add_tag[p << 1] = ((add_tag[p << 1] * mul_tag[p]) % MOD + add_tag[p]) % MOD;

    d[(p << 1) | 1] = (d[(p << 1) | 1] * mul_tag[p] + len_right * add_tag[p]) % MOD;
    mul_tag[(p << 1) | 1] = (mul_tag[(p << 1) | 1] * mul_tag[p]) % MOD;
    add_tag[(p << 1) | 1] = (add_tag[(p << 1) | 1] * mul_tag[p] + add_tag[p]) % MOD;

    mul_tag[p] = 1; 
    add_tag[p] = 0; 
}

void build(int l, int r, int p)
{
    mul_tag[p] = 1; 
    add_tag[p] = 0; 

    if (l == r) { 
        d[p] = a[l];
        return;
    }
    int m = l + ((r - l) >> 1);
    build(l, m, p << 1); 
    build(m + 1, r, (p << 1) | 1); 
    push_up(p);
}

void update_add(int L, int R, int C, int s, int t, int p)
{
    if (L <= s && t <= R) {
        d[p] += (t - s + 1) * C, d[p] %= MOD; 
        add_tag[p] += C, add_tag[p] %= MOD; 
        return;
    }
    push_down(s, t, p); 
    int m = s + ((t - s) >> 1);
    if (L <= m) 
        update_add(L, R, C, s, m, p << 1);
    if (R > m) 
        update_add(L, R, C, m + 1, t, (p << 1) | 1);
    push_up(p); 
}

void update_mul(int L, int R, int C, int s, int t, int p)
{
    if (L <= s && t <= R) {
        d[p] = d[p] * C % MOD; 
        mul_tag[p] = mul_tag[p] * C % MOD; 
        add_tag[p] = add_tag[p] * C % MOD; 
        return;
    }
    push_down(s, t, p); 
    int m = s + ((t - s) >> 1);
    if (L <= m) 
        update_mul(L, R, C, s, m, p << 1);
    if (R > m) 
        update_mul(L, R, C, m + 1, t, (p << 1) | 1);
    push_up(p); 
}

int query_sum(int L, int R, int s, int t, int p)
{
    if (L <= s && t <= R) 
        return d[p]; 
    push_down(s, t, p); 
    int m = s + ((t - s) >> 1);
    int sum = 0;
    if (L <= m) 
        sum += query_sum(L, R, s, m, p << 1), sum %= MOD;
    if (R > m) 
        sum += query_sum(L, R, m + 1, t, (p << 1) | 1), sum %= MOD;
    return sum;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) 
        cin >> a[i]; 

    build(1, n, 1); 

    for (int i = 1; i <= m; i++) {
        int op, x, y, k;
        cin >> op; 
        if (op == 1) { 
            cin >> x >> y >> k;
            update_mul(x, y, k, 1, n, 1);
        } else if (op == 2) { 
            cin >> x >> y >> k;
            update_add(x, y, k, 1, n, 1);
        } else { 
            cin >> x >> y;
            cout << query_sum(x, y, 1, n, 1) << '\n';
        }
    }

    return 0;
}